package Tree;

import java.util.*;

public class MyBinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public int nodeSize = 0;
    public int leafNodeSize = 0;

    public TreeNode creative() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        //TreeNode H = new TreeNode('H');

        A.left  = B;
        A.right = C;
        B.left  = D;
        B.right = E;
        C.left  = F;
        C.right = G;
        //E.left = H;

        return A;
    }
    // 二叉树的前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    // 二叉树的中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    // 二叉树的后序遍历
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    // 获取二叉树中的结点个数(法1)
    public int size(TreeNode root) {
        if (root == null) {
            return 0;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
        return nodeSize;
    }
    // 获取二叉树中的结点个数(法2)
    public int size2(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = size2(root.left);
        int right = size2(root.right);
        return left + right + 1;
    }
    // 获取叶子节点个数(法1)
    public int getLeafNodeSize(TreeNode root) {
        if(root == null){
            return 0;
        }
        getLeafNodeSize(root.left);
        getLeafNodeSize(root.right);
        if(root.left == null && root.right == null){
            leafNodeSize++;
        }
        return leafNodeSize;
    }
    // 获取叶子结点个数(法2)
    public int getLeafNodeSize2(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = getLeafNodeSize2(root.left);
        int right = getLeafNodeSize2(root.right);
        if(root.left == null && root.right == null){
            return 1;
        }
        return left + right;
    }
    // 获取第k层结点的个数
    public int getKLevelNodeCount(TreeNode root, int k) {
        if(root == null){
            return 0;
        }
        int left = getKLevelNodeCount(root.left,k - 1);
        int right = getKLevelNodeCount(root.right,k - 1);
        if(k == 1){
            return 1;
        }
        return left + right;
    }
    // 获取二叉树的高度
    public int TreeHeight(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftHeight = TreeHeight(root.left) + 1;
        int rightHeight = TreeHeight(root.right) + 1;
        return Math.max(leftHeight,rightHeight);
    }
    // 查找值为val的元素是否存在
    public TreeNode find(TreeNode root,char val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode left = find(root.left,val);
        if(left != null){
            return left;
        }
        TreeNode right = find(root.right,val);
        if(right != null){
            return right;
        }
        return null;
    }
    // 层序遍历
    public void levelOrder(TreeNode root){
        if(root == null){
            return;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.push(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.removeLast();
            System.out.print(node.val + " ");
            if(node.left != null){
                queue.push(node.left);
            }
            if(node.right != null){
                queue.push(node.right);
            }
        }
        System.out.println();
    }
    // 判断该二叉树是否为完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if(root == null) {
            return true;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.push(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.removeLast();
            if(cur == null){
                break;
            }
            queue.push(cur.left);
            queue.push(cur.right);
        }
        TreeNode node = queue.removeLast();
        while(!queue.isEmpty()){
            if(node != null){
                return false;
            }
            node = queue.removeLast();
        }
        return true;
    }
}


